「题解」 [HAOI2015]树上染色

Posted on Edited on

$Description$

$Solution$

分开计算每条边的贡献。

边对点产生贡献，当且仅当边的两端都有点。

于是对于$(u,fa)$，$u$的子树选中了$x$个点，我们可以分开计算白点和黑点的贡献$sum:$

$sum_{(u,fa)}=x(k-x)+(size[u]-x)(n-size[u]-k+x)$

$dp[fa][x]=dp[fa][x-y]+dp[v][y]+sum{(u,fa)}w{(u,fa)}$

把$u$打成$y$水过两个点$QWQ$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<iostream>
#include<cstring>

const int MAXN = 2010;
long long dp[MAXN][MAXN];
int siz[MAXN] = {0}, h[MAXN];
int cnt = 0, N, K;
struct E{
	int t, val, nxt;
}Ed[2 * MAXN];

void Add(int f, int t, int val){Ed[++cnt].t = t; Ed[cnt].nxt = h[f]; Ed[cnt].val = val; h[f] = cnt;}

void dfs(int k, int fa)
{
	siz[k] = 1; dp[k][0] = dp[k][1] = 0;
	for (int i = h[k]; i; i = Ed[i].nxt)
	{
		int u = Ed[i].t; if (u == fa) continue;
		dfs(u, k); siz[k] += siz[u];
		for (int x = std::min(siz[k], K); x >= 0; x--)
			for (int y = 0; y <= std::min(x, siz[u]); y++)
			{ 
				if (dp[k][x - y] == -1) continue;
				long long sum = 1LL * (K - y) * y + 1LL * (siz[u] - y) * (N - siz[u] - K + y) ;
				dp[k][x] = std::max(dp[k][x - y] + dp[u][y] + sum * Ed[i].val, dp[k][x]);
			}
	}
}

int rd()
{
	int ret = 0; char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	for(; isdigit(ch); ch = getchar()) ret = ret * 10 + (int)ch - 48;
	return ret;
}

int main()
{
	freopen("Tarly.in", "r", stdin);
	N = rd(), K = rd();
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i < N; i++) 
	{
		int f = rd(), t = rd(), v = rd(); 
		Add(f, t, v); Add(t, f, v);
	}
	dfs(1, 0);
	printf("%lld\n", dp[1][K]);
	return 0;
}